---
title: "DFS,BFS,DP的选择"
created: 2025-11-28
tags:
  - 算法
---

# DFS,BFS,DP的选择

## 宽度优先搜索（BFS）

- **适用场景**：BFS适合用来解决“最短路径”问题，如在未加权图中找到两点之间的最短路径。它也适用于层次遍历树或图、搜索最小生成树等场景。
- **优点**：BFS能够保证在找到解时，这个解是最优的（即路径最短的情况）。
- **缺点**：在最坏情况下，需要存储所有访问过的节点，可能会消耗大量内存。

## 深度优先搜索（DFS）

- **适用场景**：DFS适合用于需要探索所有可能路径的问题，如解迷宫、图的连通性、回溯算法中的排列、组合问题等。
- **优点**：DFS的空间效率高于BFS，因为它的最大空间需求仅仅是递归的深度。
- **缺点**：DFS可能会陷入死循环，需要特别处理避免重复访问。另外，它找到的路径不一定是最短的。

## 动态规划（DP）

- **适用场景**：DP适用于解决有重叠子问题和最优子结构的问题，常见于求最值问题（如最长递增子序列、最大子数组和）、计数问题（如不同路径）等。
- **优点**：DP可以通过存储子问题的解来避免重复计算，提高效率。
- **缺点**：需要仔细设计状态和状态转移方程，有时候空间复杂度较高。

## 选择指导

1. **问题类型识别**：首先识别问题类型，是寻找最短路径、需要遍历所有可能性还是有重叠子问题的最优化问题。
2. **数据规模考量**：注意到算法的时间和空间复杂度，根据问题的数据规模来判断哪种算法更适用。
3. **边界条件处理**：考虑问题的边界条件，这对于选择正确的算法和设计算法都非常重要。
4. **实现复杂度**：有时候，实现起来更简单的算法即使在理论上效率低一些，也可能是更好的选择，因为它更容易避免实现中的错误。

### 数据规模启发

（n≤30用DFS或BFS，n≤100或n≤1000用DP）是一个基本的启发式方法，可以作为初步的算法选择指南，但要记住，最合适的算法总是取决于具体问题的性质。这个规则背后的思想是考虑到算法的时间复杂度和问题规模的关系。

#### 为何n≤30适合DFS或BFS？

当n相对较小（如n≤30）时，问题的解空间不会特别大，这使得通过DFS或BFS穷举所有可能的解变得可行。DFS和BFS在这种规模的问题上能够较快地找到解，而且实现起来通常比较直接。

#### 为何n≤100或n≤1000适合DP？

对于稍大的问题规模（如n≤100或n≤1000），直接的穷举变得不再可行，这时动态规划（DP）成为更好的选择。DP通过避免重复计算相同的子问题来优化计算过程，使得算法能够在可接受的时间内解决问题。

y总考前最后一次周赛给的技巧是 如果实在不确定 就直接写两套方案

手动if if(n≤30)执行暴搜 否则执行dp 这样能保证30以内的数据一定对 然后还能尽可能多拿后面的分

### 察觉dp

#### 重叠子问题是什么？

在讨论DP时，“重叠子问题”是一个关键概念。如果在递归算法中，相同的问题被多次计算，那么这个问题就具有重叠子问题。简而言之，就是解决大问题需要反复解决一些相同的小问题。
（那就是记忆化搜索的意思了）

#### 怎样察觉重叠子问题？

1. **递归结构**：如果问题可以通过递归方式分解为更小的子问题，并且这些子问题中有很多是重复的，那么这个问题就可能有重叠子问题。比如，计算斐波那契数列中的某个数时，为了得到`fib(n)`,
   你需要计算`fib(n-1)`和`fib(n-2)`，而计算`fib(n-1)`又需要计算`fib(n-2)`和`fib(n-3)`，如此这般，`fib(n-2)`就被重复计算了多次。
2. **子问题的数量**：当递归解决一个问题时，如果子问题的总数（不考虑重复）远小于递归过程中生成的总调用数量，那么这个问题很可能就有大量的重叠子问题。
3. **问题的描述**：某些类型的问题，如路径问题（寻找从点A到点B的最短/最长路径）、分割问题（如将数字或字符串分割为满足某些条件的部分），经常会有重叠子问题。

#### 有什么特征？

- **递归解法的效率低下**：如果一个递归解法的执行时间远远高于其它方法，这可能是因为它在浪费时间重复计算相同的子问题。
- **可以通过分解问题为较小部分来解决**：如果可以将问题分解成较小的部分，并且这些小部分之间存在明显的相似性，这就是重叠子问题的一个明显特征。

---
⬅️ [[DFS BFS相关模型|DFS BFS相关模型]] 🏠 [[00-刷题理模型]] ➡️ [[DFS|DFS]]